package ljl.codetop300;

import commons.TreeNode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _106_build_tree {

  /**
   * 路飞的解法我还是没记住，还是用剑指offer的解法吧我先，那个我背的比较熟
   * 剑指offer上是 前中序，这个是后序，我背错了
   */
  static class tes {

    public static void main(String[] args) {
      new tes().buildTree(new int[] {9,3,15,20,7}, new int[] {9,15,7,20,3});
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
      return build(inorder, 0, postorder, 0, inorder.length);
    }
    TreeNode build(int[] inorder, int from1, int[] postorder, int from2, int len1) {
      if (len1 <= 0) return null;
      int value = postorder[from2 + len1 - 1];
      TreeNode root = new TreeNode(value);
      int len = 0;
      int p = from1;
      while (inorder[p] != value) {
        p++;
        len++;
      }
      root.left = build(inorder, from1, postorder, from2, len);
      root.right = build(inorder, p + 1, postorder, from2 + len, len1 - len - 1);
      return root;
    }
  }

  static class off_recur {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer, Integer> idx_map = new HashMap<>();

    /**
     * @param left 左孩子起始位置
     * @param right 右孩子起始位置
     */
    public TreeNode helper(int left, int right) {
      if (left > right) {
        return null;
      }
      int root_val = postorder[post_idx];
      TreeNode root = new TreeNode(root_val);
      int index = idx_map.get(root_val);
      post_idx--;
      // 这个解法有一个问题，必须先 right 后 left
      root.right = helper(index + 1, right);
      root.left = helper(left, index - 1);
      return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
      this.postorder = postorder;
      this.inorder = inorder;
      post_idx = postorder.length - 1;
      int idx = 0;
      for (Integer val : inorder) {
        idx_map.put(val, idx++);
      }
      return helper(0, inorder.length - 1);
    }
  }

  static class copy_off_recur {
    Map<Integer, Integer> valueToInorderIndexMap = new HashMap<>();
    int postIndex;
    int[] inorder, postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
      this.inorder = inorder;
      this.postorder = postorder;
      postIndex = inorder.length - 1;
      int idx = 0;
      for (int i : inorder) {
        valueToInorderIndexMap.put(i, idx++);
      }
      return build(0, postIndex);
    }
    TreeNode build(int leftIndex, int rightIndex) {
      // 相等说明只有一个节点了 可不能跳过
      if (leftIndex > rightIndex) return null;
      int rootVal = postorder[postIndex--];
      TreeNode root = new TreeNode(rootVal);
      int rootIndex = valueToInorderIndexMap.get(rootVal);
      root.right = build(rootIndex + 1, rightIndex);
      root.left = build(leftIndex, rootIndex - 1);
      return root;
    }
  }
  static class off_iter {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
      if (postorder == null || postorder.length == 0) {
        return null;
      }
      TreeNode root = new TreeNode(postorder[postorder.length - 1]);
      Deque<TreeNode> stack = new LinkedList<>();
      stack.push(root);
      int inorderIndex = inorder.length - 1;
      for (int i = postorder.length - 2; i >= 0; i--) {
        int postorderVal = postorder[i];
        TreeNode node = stack.peek();
        if (node.val != inorder[inorderIndex]) {
          node.right = new TreeNode(postorderVal);
          stack.push(node.right);
        } else {
          while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
            node = stack.pop();
            inorderIndex--;
          }
          node.left = new TreeNode(postorderVal);
          stack.push(node.left);
        }
      }
      return root;
    }
  }

  static class copy_off_iter {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
      int len = inorder.length;
      LinkedList<TreeNode> stack = new LinkedList<>();
      TreeNode root = new TreeNode(postorder[len - 1]);
      stack.push(root);
      int inorderIndex = len - 1;
      for (int i = len - 2; i >= 0; i--) {
        int postVal = postorder[i];
        TreeNode node = stack.peek();
        if (node.val != inorder[inorderIndex]) {
          node.right = new TreeNode(postVal);
          stack.push(node.right);
        } else {
          while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
            node = stack.pop();
            inorderIndex--;
          }
          node.left = new TreeNode(postVal);
          stack.push(node.left);
        }
      }
      return root;
    }
  }

}
